package com.dyz.otherAlgorithm;

/**
 * @author: daiyizheng
 * @date: 2021/6/28 23:36
 * @description:
 */
public class EightQueue {
    public static void main(String[] args) {
        new EightQueue().placeQueues(4);
    }


    /**
     * 数组索引是行号，数组元素是列号
     */
    int [] cols;
    /**
     * 一共多少种摆法
     */
    int ways;

    public void placeQueues(int n){
        if(n<1){return;}
        cols = new int[n];
        place(0);
        System.out.println(n+"皇后一共有"+ways+"种摆法");
    }

    private void place(int row) {
        //递归中止条件
        if(row==cols.length){
            ways++;
            show();
            return;
        }
        //递归
        for (int col=0; col<cols.length;col++){
            if(isValid(row, col)){
                //在第row行第col列摆放皇后
                cols[row]=col;
                place(row+1);
            }
        }
    }

    private boolean isValid(int row, int col) {
        for (int i=0; i<row; i++){
            //第col列已经有皇后了
            if(cols[i]==col){
                System.out.println("["+row+"]"+"["+col+"]"+"="+"False");
                return false;
            }
            //第i行的皇后跟第row行第col列处在同一个斜线上
            if(row-i==Math.abs(col-cols[i])){
                System.out.println("["+row+"]"+"["+col+"]"+"="+"False");
                return false;
            }
        }
        System.out.println("["+row+"]"+"["+col+"]"+"="+"true");
        return true;
    }

    private void show() {
        for (int row=0; row<cols.length;row++){
            for (int col=0; col<cols.length;col++){
                if(cols[row] == col){
                    System.out.print("1 ");
                }else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("---------------------");
    }
}
